<html>
<head><meta charset="utf-8"><title>Use better data structure for result of `associated_items` · t-compiler · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/index.html">t-compiler</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html">Use better data structure for result of `associated_items`</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="187859120"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187859120" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187859120">(Feb 10 2020 at 21:18)</a>:</h4>
<p><a href="https://github.com/rust-lang/rust/issues/68957" target="_blank" title="https://github.com/rust-lang/rust/issues/68957">#68957</a> is a performance problem caused by <code>O(n)</code> lookup for associated items by name. It seems that searching through all associated items for one with a particular name is a common pattern. The obvious solution is to use a better data structure, but the result of the <code>associated_items</code> query needs to be interned. Do we currently intern hashmaps or btrees? If we don't and it's hard to do, we could sort the list of associated items by name before interning.</p>
<p>cc <span class="user-mention" data-user-id="116118">@Matthew Jasper</span></p>



<a name="187860347"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187860347" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Wesley Wiser <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187860347">(Feb 10 2020 at 21:30)</a>:</h4>
<blockquote>
<p>Do we currently intern hashmaps or btrees?</p>
</blockquote>
<p>Yes. For example, the <code>wasm_import_module_map</code> query returns a <code>&amp;'tcx FxHashMap&lt;DefId, String&gt;</code>.</p>
<p>Query definition: <a href="https://github.com/rust-lang/rust/blob/4ff8fb9cb210a9f06e0eafc364bd12de2b67f087/src/librustc/query/mod.rs#L200" target="_blank" title="https://github.com/rust-lang/rust/blob/4ff8fb9cb210a9f06e0eafc364bd12de2b67f087/src/librustc/query/mod.rs#L200">https://github.com/rust-lang/rust/blob/4ff8fb9cb210a9f06e0eafc364bd12de2b67f087/src/librustc/query/mod.rs#L200</a></p>
<p>Query implementation: <a href="https://github.com/rust-lang/rust/blob/a29424a2265411dda7d7446516ac5fd7499e2b55/src/librustc_codegen_llvm/attributes.rs#L429" target="_blank" title="https://github.com/rust-lang/rust/blob/a29424a2265411dda7d7446516ac5fd7499e2b55/src/librustc_codegen_llvm/attributes.rs#L429">https://github.com/rust-lang/rust/blob/a29424a2265411dda7d7446516ac5fd7499e2b55/src/librustc_codegen_llvm/attributes.rs#L429</a></p>



<a name="187860857"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187860857" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187860857">(Feb 10 2020 at 21:35)</a>:</h4>
<p>Good! My next question is what we should index on. It seems like most code that searches for an item by name uses <code>hygienic_eq</code>, but some uses non-hygienic comparison for well-known traits. Seems like we either want a multi-map from <code>Symbol</code> to <code>AssocItem</code> or to use hygienic comparison everywhere and incorporate that information into the key.</p>



<a name="187861124"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187861124" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187861124">(Feb 10 2020 at 21:38)</a>:</h4>
<p>So something like <code>(AssocItemKind, Symbol, {hygiene info}) -&gt; AssocItem</code></p>



<a name="187861130"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187861130" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187861130">(Feb 10 2020 at 21:38)</a>:</h4>
<p><a href="https://github.com/rust-lang/rust/blob/e6ec0d125eba4074122b187032474b4174fb9d31/src/librustc_mir_build/hair/cx/mod.rs#L173" target="_blank" title="https://github.com/rust-lang/rust/blob/e6ec0d125eba4074122b187032474b4174fb9d31/src/librustc_mir_build/hair/cx/mod.rs#L173">https://github.com/rust-lang/rust/blob/e6ec0d125eba4074122b187032474b4174fb9d31/src/librustc_mir_build/hair/cx/mod.rs#L173</a></p>
<p>(unhygienic comparison)</p>



<a name="187861288"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187861288" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187861288">(Feb 10 2020 at 21:40)</a>:</h4>
<p>Does anyone object to me sorting the result of <code>associated_items</code> by <code>Symbol</code> for now and adding an efficient <code>find_with_name_unhygienic</code> method to it?</p>



<a name="187861354"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187861354" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187861354">(Feb 10 2020 at 21:40)</a>:</h4>
<p>Do we want to avoid actually computing <code>{hygiene info}</code> for performance reasons? I know nothing about this.</p>



<a name="187861484"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187861484" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187861484">(Feb 10 2020 at 21:42)</a>:</h4>
<p>I briefly looked into this and it seemed like some passes rely on these items being in definition order</p>



<a name="187861616"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187861616" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187861616">(Feb 10 2020 at 21:43)</a>:</h4>
<p><span class="user-mention" data-user-id="211727">@Jonas Schievink</span> That's good to know. We can still do this while preserving definition order. But we won't be able to use data structures in <code>std</code>.</p>



<a name="187861696"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187861696" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187861696">(Feb 10 2020 at 21:44)</a>:</h4>
<p>Unless someone added an insertion-order preserving <code>HashMap</code> while I wasn't paying attention.</p>



<a name="187862117"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187862117" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187862117">(Feb 10 2020 at 21:49)</a>:</h4>
<p>I'm gonna go ahead and claim <a href="https://github.com/rust-lang/rust/issues/68957" target="_blank" title="https://github.com/rust-lang/rust/issues/68957">#68957</a>. It seems like we may want to audit the places that depend on definition order and stop looking up particular items on known traits by name (perhaps these should be lang items instead?). However, I don't think this should block resolving <a href="https://github.com/rust-lang/rust/issues/68957" target="_blank" title="https://github.com/rust-lang/rust/issues/68957">#68957</a>.</p>



<a name="187862466"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187862466" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187862466">(Feb 10 2020 at 21:53)</a>:</h4>
<p><span class="user-mention" data-user-id="119009">@eddyb</span> has suggested the same, and I agree</p>



<a name="187862580"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187862580" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187862580">(Feb 10 2020 at 21:54)</a>:</h4>
<p>definitely on the lang items, they are basically free and we should use them as much as possible</p>



<a name="187862655"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187862655" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187862655">(Feb 10 2020 at 21:55)</a>:</h4>
<p>but also I've wanted method lookup to be faster for years, I just kept forgetting about it lol</p>



<a name="187862806"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187862806" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187862806">(Feb 10 2020 at 21:57)</a>:</h4>
<p>I'm happy to take this on. I'll start with the method lookup part and then start converting things to lang items</p>



<a name="187862848"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187862848" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187862848">(Feb 10 2020 at 21:57)</a>:</h4>
<p>the lang item part is easier and less controversial, I would do it separately I think</p>



<a name="187862960"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187862960" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187862960">(Feb 10 2020 at 21:59)</a>:</h4>
<p>Just lang items won't solve <a href="https://github.com/rust-lang/rust/issues/68957" target="_blank" title="https://github.com/rust-lang/rust/issues/68957">#68957</a> though.</p>



<a name="187863037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187863037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187863037">(Feb 10 2020 at 22:00)</a>:</h4>
<p>So I'd like to prioritize efficient method lookup over that</p>



<a name="187863136"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187863136" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Dylan MacKenzie (ecstatic-morse) <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187863136">(Feb 10 2020 at 22:00)</a>:</h4>
<p>Not that they're mutually exclusive, and learning a bit more about hygiene/hygienic_eq would be beneficial before tackling method lookup.</p>



<a name="187868244"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Use%20better%20data%20structure%20for%20result%20of%20%60associated_items%60/near/187868244" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Use.20better.20data.20structure.20for.20result.20of.20.60associated_items.60.html#187868244">(Feb 10 2020 at 23:04)</a>:</h4>
<p>ah sure</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>